#include<vector>
#include<algorithm>
using namespace std;
struct ListNode
{
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* div_list(ListNode* head){
        ListNode* s=head,*f=head;
        ListNode* pev=s;
        while(f&&f->next){
            pev=s,s=s->next,f=f->next->next;
        }
        pev->next=nullptr;
        return s;
    }
    ListNode* reverse_list(ListNode* head){
        ListNode* pev=nullptr,*cur=head;
        while(cur){
            ListNode*next=cur->next;
            cur->next=pev,pev=cur,cur=next;
        }
        return pev;
    }
    int pairSum(ListNode* head) {
        ListNode* add_head=reverse_list(div_list(head));
        int ans=head->val;
        while(head){
            ans=max(ans,head->val+add_head->val);
            head=head->next,add_head=add_head->next;
        }
        return ans;
    }
};
class Solution
{
public:
    int pairSum(ListNode* head)
    {
        int num = 0;
        for (ListNode* cur = head; cur; cur = cur->next)
            num++;
        vector<int> add(num / 2, 0);
        int i = 0;
        for (ListNode* cur = head; cur; cur = cur->next)
            i < num / 2 ? add[i++] += cur->val : add[num - i++ - 1] += cur->val;
        return *max_element(add.begin(), add.end());
    }
};